package com.ztom.top100;

/**
 * 实现 Trie (前缀树)
 * <p>
 * https://leetcode-cn.com/problems/implement-trie-prefix-tree/
 *
 * @author ZhangTao
 */
public class Code62Trie {

    class Trie {

        private Node root;

        public Trie() {
            this.root = new Node();
        }

        public void insert(String word) {
            if (word == null || word.length() == 0) {
                return;
            }
            char[] str = word.toCharArray();
            Node node = root;
            node.pass++;
            int path = 0;
            for (char c : str) {
                path = c - 'a';
                if (node.nexts[path] == null) {
                    node.nexts[path] = new Node();
                }
                node = node.nexts[path];
                node.pass++;
            }
            node.end++;
        }

        public boolean search(String word) {
            if (word == null || word.length() == 0) {
                return false;
            }
            char[] str = word.toCharArray();
            Node node = root;
            int path = 0;
            for (char c : str) {
                path = c - 'a';
                if (node.nexts[path] == null) {
                    return false;
                }
                node = node.nexts[path];
            }
            return node.end > 0;
        }

        public boolean startsWith(String prefix) {
            if (prefix == null || prefix.length() == 0) {
                return false;
            }
            char[] str = prefix.toCharArray();
            Node node = root;
            int path = 0;
            for (char c : str) {
                path = c - 'a';
                if (node.nexts[path] == null) {
                    return false;
                }
                node = node.nexts[path];
            }
            return node.pass > 0;
        }


        private class Node {
            private int pass;
            private int end;
            private Node[] nexts;

            public Node() {
                this.nexts = new Node[26];
            }
        }
    }
}
